package com.ryujung.binary_tree.leetCode_109;


class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }

    @Override
    public String toString() {
        return "TreeNode{" +
                "val=" + val + (left == null && right == null ? "" :
                (left == null ? "," : ",\n") + " left=" + left +
                        (right == null ? "," : ",\n") + " right=" + right +
                        '}');
    }
}

class Solution {
    /**
     * 一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差不超过 1。
     * <p>
     * 思路:
     * 使用分治来解决,每次从根节点遍历
     */
    public TreeNode sortedListToBST1(ListNode head) {
        if (head == null) return null;

        int len = 0;
        ListNode h = head;
        while (head != null) {
            len++;
            head = head.next;
        }

        return buildBST1(h, 0, len - 1);
    }

    public TreeNode buildBST1(ListNode head, int left, int right) {
        if (left > right) return null;

        int mid = (left + right + 1) >>> 1;
        TreeNode root = new TreeNode();
        root.left = buildBST1(head, left, mid - 1);
        root.right = buildBST1(head, mid + 1, right);

        for (int i = 0; i < mid; i++) {
            head = head.next;
        }
        root.val = head.val;
        return root;
    }
    // 时间复杂度：O(n*logn) 需要完整遍历链表n ，遍历每个节点时，还需要遍历0~mid个元素（logn），故n*logn
    // 空间复杂度：O(logn) 递归所需的栈空间大小，与树的深度有关
    // 平衡二叉树的高度和节点数量之间的关系是O(logn)。故O(height) = O(logn) ,n为节点数量

    /**
     * 想法:
     * 链表是否可以看做一个二叉树的中序遍历？
     * 尝试通过递归方式从二叉树的左子树开始构建，……
     * <p>
     * 思路：
     * 使用分治和中序遍历优化链表
     * 获取链表的长度，然后将 将 0~len 构建二叉树，
     * 将每次构建都视为一次中序遍历，链表直接从左子树开始构建，然后再构建根节点，然后右子树
     */
    ListNode globalHead;

    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) return null;

        globalHead = head;
        // 正序排列的链表可以视为二叉树的中序遍历
        // 根据这个特点，来优化原来的分治算法
        int len = 0;
        while (head != null) {
            head = head.next;
            len++;
        }
        return buildBST(0, len - 1);
    }

    public TreeNode buildBST(int l, int r) {
        if (l > r) return null;

        int mid = (l + r + 1) >>> 1;
        // 根据中序遍历，从左子树开始构建
        TreeNode root = new TreeNode();
        root.left = buildBST(l, mid - 1);

        // 根节点
        root.val = globalHead.val;
        globalHead = globalHead.next;

        // 右子树
        root.right = buildBST(mid + 1, r);
        return root;
    }
    // 时间复杂度：O(n) 每次只需遍历链表二次
    // 空间复杂度：O(logn) 递归所需栈空间大小，取决于平衡树的高度——logn。

/**
 * 尝试暴力破解，将链表转化为数组，
 * 再将数组视为二叉树的中序遍历，构建对应的二叉树
 * <p>
 * 从二叉树的左子树开始构建，
 * 判断当前设置的根节点左树是否为空，
 * 如果为空，则将当前节点加入左子树
 * 如果不为空，
 * 判断根节点右子树是否为空，
 * 如果为空，则将当前节点设为根节点的右子树，并将当前节点的left指向根节点的左节点
 * 如果不为空，判断右子树的left是否指向左节点，
 * 如果是指向左节点，则将右子树设为新的根节点newRoot，
 * 并将当前节点置于右子树，并重置root，将root左指向newRoot(保持root右为空)
 * <p>
 * // 以上方法过于复杂，存在bug，部分情况左右子树高出差超过1，不符合题意
 * <p>
 */
}